function BinarySearchTree() {

  // 封装内部结点类
  function Node(key) {
    this.key = key
    this.left = null
    this.right = null
  }

  this.root = null

  // 方法
  // 1.插入方法
  BinarySearchTree.prototype.insert = function(key) {
    // >1.根据key创建结点
    let newNode = new Node(key)

    // >2.判断二叉树是否为空
    if (this.root === null) {
      this.root = newNode
      return this // 返回当前二叉树
    }

    // >3.插入结点（开始左右比较，使用递归得到最终比较的结点，将newNode插入到该节点之后）
    this.insertNode(this.root, newNode)
    return this
  }

  // 递归判断插入
  BinarySearchTree.prototype.insertNode = function(node, newNode) {
    if (newNode.key < node.key) {
      if (node.left === null) {
        return node.left = newNode
      }
      this.insertNode(node.left, newNode)
    } else {
      if (node.right === null) {
        return node.right = newNode
      }
      this.insertNode(node.right, newNode)
    }
  }

  // 2. 二叉搜索树的遍历
  // >1.先序遍历
  BinarySearchTree.prototype.preOrderTranversal = function(handler) {
    this.preOrderTranversalNode(this.root, handler)
  }

  // 先序遍历递归操作
  BinarySearchTree.prototype.preOrderTranversalNode = function(node, handler) {
    if (node != null) {
      handler(node.key)

      // 递归遍历左节点
      this.preOrderTranversalNode(node.left, handler)

      // 递归遍历右节点
      this.preOrderTranversalNode(node.right, handler)
    }
  }

  // >2.中序遍历
  BinarySearchTree.prototype.midOrderTranversal = function(handler) {
    this.midOrderTranversalNode(this.root, handler)
  }

  // 中序遍历递归操作
  BinarySearchTree.prototype.midOrderTranversalNode = function(node, handler) {
    if (node != null) {
      // 递归遍历左节点
      this.midOrderTranversalNode(node.left, handler)
      handler(node.key)

      // 递归遍历右节点
      this.midOrderTranversalNode(node.right, handler)
    }
  }

  // >3.后序遍历
  BinarySearchTree.prototype.backOrderTranversal = function(handler) {
    this.backOrderTranversalNode(this.root, handler)
  }

  //后序遍历递归
  BinarySearchTree.prototype.backOrderTranversalNode = function(node, handler) {
    if (node != null) {
      // 递归遍历左节点
      this.backOrderTranversalNode(node.left, handler)

      // 递归遍历右节点
      this.backOrderTranversalNode(node.right, handler)

      console.log(node.key);
    }
  }

  //3.获取最值
  // >1.最大值
  BinarySearchTree.prototype.min = function() {
    let crt = this.root
    while (crt.left) crt = crt.left
    return crt.key
  }

  // >2.最小值
  BinarySearchTree.prototype.max = function() {
    let crt = this.root
    while (crt.left) crt = crt.right
    return crt.key
  }

  // 4.搜素方法
  BinarySearchTree.prototype.search = function(key) {
    let crt = this.root
    while (crt != null) {
      if (key < crt.key) crt = crt.left
      else if (key > crt.key) crt = crt.right
      else return true
    }
    return false
  }

  // 5.删除节点(删除一个) ---> 如何删除多个？
  BinarySearchTree.prototype.remove = function(key) {
    // >1查找到对应的结点（需要三个变量，当前查找到的节点的父节点，父节点的left,父节点的right）

    let crt = this.root // 当前节点
    let fNode = null // 记录当前节点的父节点
    while (crt) {
      if (crt.key < key) {
        fNode = crt
        crt = crt.right
      } else if (crt.key > key) {
        fNode = crt
        crt = crt.left
      } else {
        // > 1.1查找到该节点了
        // >2.根据条件删除节点
        if (!crt.left && !crt.right) {
          // >2.1找到的节点为叶节点
          // 找到的节点为根节点，没有父节点
          if (fNode === null) {
            this.root = null
            return true
          }
          fNode.left === crt ? fNode.left = null : fNode.right = null
        } else if (crt.left && crt.right) {

          // >2.1找到的节点有两个子节点
          if (fNode === null) {
            this.root.left.right = this.root.right
            this.root = this.root.left
            return true
          }
          // 找到前驱或者后继
          let crt1 = crt // 寻找crt子树中的前驱
          let fCrt1 = null // crt1的父节点
          while (crt1.left) {
            fCrt1 = crt1
            crt1 = crt1.left
          }


          crt1.left = crt.left
          crt1.right = crt.right

          // 要删除的节点是其父节点的左节点
          if (fNode.left === crt) {
            fNode.left = crt1
          } else {
            // 要删除的节点是其父节点的右节点
            fNode.right = crt1
          }

          fCrt1.left === crt1 ? fCrt1.left = null : fCrt1.right = null

        } else {
          // >2.2找到的节点有一个子节点
          // 找到的节点为根节点，没有父节点
          if (fNode === null) {
            if (this.root.left) this.root.left = this.root
            else this.root.right = this.root
            return true
          }
          if (crt.left) {
            fNode.left === crt ? fNode.left = crt.left : fNode.right = crt.left
          } else {
            fNode.left === crt ? fNode.left = crt.right : fNode.right = crt.right
          }
        }

      }
    }

    // > 1.2 没有找到该节点
    return false
  }
}

module.exports = BinarySearchTree

let b = new BinarySearchTree()
b.insert(2).insert(1).insert(3)
console.log(b.remove(1));
// b.insert(4).insert(3).insert(6).insert(7).insert(2).insert(9).insert(5).insert(1).insert(1).insert(4).insert(2).insert(5).insert(6)

// b.preOrderTranversal(function(key) {
//   console.log(key);
// })
// console.log('-----');
// b.midOrderTranversal(function(key) {
//   console.log(key);
// })
// console.log('------');
// b.backOrderTranversal(function(key) {
//   console.log(key);
// })

// console.log(b.max());
// console.log(b.min());
// console.log(b.search(111));

b.insert(5).insert(4).insert(3).insert(2)